/*
  Maximum sum
 【题目描述】
    对于给定的整数序列 A = {a1, a2, ... , an}，找出两个不重合连续子段，
    使得两子段中所有数字的和最大。
    我们如下定义函数 d(A)：
                                          t1     t2
      d(A) =           max              { ∑ ai + ∑ aj }
             1 ≤ s1 ≤ t1 < s2 ≤ t2 ≤ n    i=s1   j=s2
    我们的目标就是求出d(A)。
 【输入】
    第一行是一个整数 T ( ≤ 30)，代表一共有多少组数据。
    接下来是 T 组数据。
    每组数据的第一行是一个整数，代表数据个数据 n (2 ≤ n ≤ 50000) ,
    第二行是 n 个整数 a1, a2, ... , an (|ai| ≤ 10000)。
 【输出】
    输出一个整数，就是d(A)的值。
 【输入样例】
    1
    10
    1 -1 2 2 3 -3 4 -4 5 -5
 【输出样例】
    13
 【提示】
    就是求最大子段和问题，样列取 2, 2, 3, −3, 4和5，Baidu搜POJ 2479 Maximum sum，
    可获得大量经典最大子段和问题的题目解析，本题 O(n2)算法超时，必须用O(n)算法。
*/